#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* res = nullptr;
    auto dfs = [&](auto&& dfs, TreeNode* root)->bool {
        if (root == nullptr) return false;
        bool left = dfs(dfs, root->left);
        bool right = dfs(dfs, root->right);
        if ((left && right) || (root->val == p->val || root->val == q->val) && (left || right)) {
            res = root;
        }
        return left || right || (root->val == p->val || root->val == q->val);
        };

    dfs(dfs, root);
    return res;
}